//接雨水
/*给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 */
 class Solution {
public:
    int trap(vector<int>& height) {
        int leftmax = 0;
        int rightmax = 0;
        int left = 0, right = height.size() - 1;
        int sum = 0;
        while (left < right) {
            sum += height[left] < leftmax ? leftmax - height[left] : 0;
            sum += height[right] < rightmax ? rightmax - height[right] : 0;
            leftmax = max(leftmax, height[left]);
            rightmax = max(rightmax, height[right]);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return sum;
    }
};